The present invention relates to the display of image data as a collection of picture elements (or pixels), and particularly relates to the display of color image data as a collection of picture elements wherein the variety of colors of the image data is greater than the variety of colors available for each picture element.
For example, color images may be displayed on black and white CRT displays (or flat panel displays or printers), but some information will be lost. Typically, for black and white displays, the value (or grayscale value) of each pixel of the image is compared to a threshold value, and if it is above the threshold then the pixel appears black, and if it is below the threshold then the pixel appears white. The difference between the greyscale value of an image pixel and the threshold is known as a pixel's error.
Dithering, or halftoning, refers to a variety of techniques that have been developed to distribute each pixel's error among neighboring pixels. For example, the Floyd and Steinberg method processes the input image in a linear fashion, scanning pixels from left to right and from top to bottom. See Robert W. Floyd and Louis Steinberg, An Adaptive Algorithm for Spatial Grayscale, Proceedings of the Society for Information Display, v.17, pp. 75-77 (1976). At each step of the Floyd and Steinberg method, the grayscale value of the current pixel (which is represented as an integer between 0 and 255), is compared to some threshold value, typically 128. Grayscale values above 128 are displayed as black, and grayscale values of 128 and below are displayed as white. The error for each pixel is distributed to four neighboring pixels that have not yet been processed. Specifically, and with reference to FIG. 1 of the drawings, the error for a pixel in row "r" and column "c" (P.sub.r,c) is distributed to pixels P.sub.r,c+1, P.sub.r+1,c+1, P.sub.r+1,c, and P.sub.r+1,c-1. The pixel error is distributed with weights of 7/16 for P.sub.r,c+1, 1/16 for P.sub.r+1,c+1, 5/16 for P.sub.r+1,c, and 3/16 for P.sub.r+1,c-1.
The Floyd and Steinberg process is time consuming, and typically requires five floating-point multiplications and five memory accesses to process each pixel of the image. For an image with dimensions "n" by "m" this typically takes 10.times.n.times.m operations. The method is also, therefore, computationally expensive.
More elaborate dithering methods have further been proposed in which each pixel's error is distributed to up to 12 neighboring unprocessed pixels in accordance with various weight distributions. These algorithms produce displays of improved image quality over the Floyd and Steinberg method, but are more computationally expensive, requiring 24.times.n.times.m floating point multiplications and memory accesses for each n by m image. See J. F. Jarvis, C. N. Judice and W. H. Kinke, A Survey of Techniques for the Display of Continuous Tome Pictures on Bi-Level Displays, Computer Graphics and Image Processing, v.5, p.13-40 (1976); and P. Stucki, MACCA--A Multiple Error Correcting Algorithm For Bi-Level Image Hard Copy Reproduction, Research Report RZ1060, IBM Research Laboratory, Zurich, Switzerland (1981).
U.S. Pat. No. 5,553,165 discloses a method of parallel error diffusion. In the method of the '165 patent, the image is processed in a conventional top down, line by line left to right order. With reference to FIG. 2 of the drawings, two or more processors (P and Q) are employed to process the image by having each processor scan the image along different rows, slightly offset from one another. Error diffusion data is written to and read from a memory unit that is shared between the processors. The method of the '165 patent, however, is still rather time consuming because the memory unit must be continuously accessed by both processors, and because each pixel must be accessed twice. Using additional processors in the method of the '165 patent in turn requires more interaction between the processors and sharing of data via common memory.
Dithering requires that a pixel be processed only after all of the pixels from which it depends have been processed. The use of multiple processors, therefore, has been of only marginal benefit because some processors will be required to wait for others. Moreover, the processors in a multiprocessor system must share memory, and each pixel may be required to be accessed at least twice. Further, the number of processors may not be easily changed in a parallel dithering system such as that of the '165 patent without reconfiguring the physical system. There is a need, therefore, for a more efficient method of dithering.